package leetcode.D1000.T934;

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    private final static int[] dx = {0, 0, -1, 1};
    private final static int[] dy = {-1, 1, 0, 0};
    private class Node {
        int x;
        int y;
        int step;
        public Node() {
        }
        public Node(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
    public int shortestBridge(int[][] A) {
        int n = A.length, minNum = Integer.MAX_VALUE;
        boolean flag = false;
        for(int i=0; i<n; ++i) {
            for(int j=0; j<n; ++j) {
                if(A[i][j] == 1) {
                    if(!flag) {
                        dfs(A, i, j, n);
                        flag = true;
                    } else {
                        int num = bfs(A, i, j, n);
                        minNum = Math.min(minNum, num);
                    }
                }
            }
        }
        return minNum;
    }
    private void dfs(int[][] A, int x, int y, int n) {
        A[x][y] = 2;
        for(int i=0; i<4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= n || A[nx][ny] != 1) {
                continue;
            }
            dfs(A, nx, ny, n);
        }
    }
    private int bfs(int[][] A, int x, int y, int n) {
        Deque<Node> dq = new LinkedList<>();
        dq.addLast(new Node(x, y, 0));
        while(!dq.isEmpty()) {
            Node top = dq.removeFirst();
            A[top.x][top.y] = 1;
            for(int i=0; i<4; ++i) {
                int nx = top.x + dx[i], ny = top.y + dy[i];
                if(nx < 0 || nx >= n || ny < 0 || ny >= n || A[nx][ny] == 1) {
                    continue;
                }
                if(A[nx][ny] == 2) {
                    return top.step;
                }
                dq.addLast(new Node(nx, ny, top.step+1));
            }
        }
        return Integer.MAX_VALUE;
    }
}
